/**
 * 输入某二叉树的前序遍历和中序遍历的结果,请重建出二叉树,
 * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字
 * 例如:输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历{4,7,2,1,5,3,8,6},则重建二叉树并返回.
 *
 */
public class suanfa07 {
    public class  TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }

    }
    public TreeNode reConstructBinaryTreeCore(int [] pre,int preStart, int preEnd,int []
            in, int inStart, int inEnd) {
        if(preStart > preEnd || inStart > inEnd){
            return null;
        }
        TreeNode root = new TreeNode(pre[preStart]);
        int i = inStart;
        for(; i <= inEnd; i++){ //在中序序列中，找根节点，可以将数组划分为两部分
            if(in[i] == pre[preStart]){
                //前序的第一个节点，是root，能将中序划分为两部分
                //一棵树，无论前，中，后怎么遍历，元素的个数是不变的
                //在实际遍历的时候，前，中，后序遍历，各种遍历方式左右子树的节点都是在一起的
                //所以这里重点是要想清楚下标问题
                //根据中序，我们能确认左子树的节点个数是：i - inStart (没有从0开始哦)
                //所以，需要从preStart+1，连续i - inStart个元素，就是左子树的前序序列
                root.left = reConstructBinaryTreeCore(pre,preStart+1, i-inStart+preStart,
                        in, inStart, i-1);
                //右子树同理
                root.right = reConstructBinaryTreeCore(pre, i-inStart+preStart+1,preEnd,
                        in, i+1, inEnd);
                break;
            }
        }
        return root;
    }
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if( pre.length == 0 || in.length == 0){
            return null;
        }
            //理论上，可以新建数组，保存前序，中序子序列，但是就需要花费额外空间
            //所以，我们采取在原数组内进行操作
            //使用闭区间限定数组范围
        return reConstructBinaryTreeCore(pre, 0, pre.length-1, in, 0, in.length-1);
    }
}
